/*
7-1 修理牧场（25 分）
	农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数L​i个长度单位，于是他购买了
	一条很长的、能锯成N块的木头，即该木头的长度是L​i的总和。

	但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。
	例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；
	第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，
	则第二次锯木头花费15，总花费为35（大于32）。请编写程序帮助农夫计算将木头锯成N块的最少花费。

	输入格式:
	输入首先给出正整数N（≤10​4​ ），表示要将木头锯成N块。第二行给出N个正整数（≤50），表示每段木块的长度。

	输出格式:
	输出一个整数，即将木头锯成N块的最少花费。

	输入样例:
	8
	4 5 1 2 1 3 1 1
	输出样例:
	49
*/


#include <iostream>
#include <stack>
#include <stdio.h>
using namespace std;
class Data
{
public:
	int oneCost;
	Data() { oneCost = 0; }
};
class Node
{
public:
	Data info;
	Node *left;
	Node *right;
	Node() { left = nullptr; right = nullptr; }
	Node(int cost) { info.oneCost = cost; }
};
void quickSortAsc(Node *data, int low, int high)
{
	if (low >= high)
		return;
	int start = low;
	int end = high;
	Node key = data[start];
	while (start < end)
	{
		while (start < end&&key.info.oneCost <= data[end].info.oneCost)
			end--;
		data[start] = data[end];
		while (start < end&&key.info.oneCost >= data[start].info.oneCost)
			start++;
		data[end] = data[start];
	}
	data[start] = key;
	quickSortAsc(data, 0, start - 1);
	quickSortAsc(data, start + 1, high);
}
class LeastCost
{
private:
	Node *root;
	int leavesNum;
	int sum;
public:
	LeastCost() { root = nullptr; sum = 0; }
	void creatTree(Node *data, int length)
	{
		leavesNum = length;
		if (data == nullptr || length == 0)  //空树时，结束创建
			return;
		if (length == 1)  //只有一个节点时，即为根节点
		{
			root = new Node(data[0]);
			return;
		}
		int i = 0;
		Node *rLSum, *l, *r, tempRoot;
		while (i < length - 1)
		{
			quickSortAsc(data, i, length - 1);   //把节点按照权重排序
			l = new Node(data[i++]);
			r = new Node(data[i++]);    //l指向的位置在r的左边
			rLSum = new Node(l->info.oneCost + r->info.oneCost);
			rLSum->left = l;
			rLSum->right = r;
			//定义一个节点的权值为其左右子树之和
			data[--i].info.oneCost = rLSum->info.oneCost;
			data[i].left = rLSum->left;
			data[i].right = rLSum->right;
			delete rLSum;
		}
		root = new Node(data[length - 1]);
	}
	void PreOrderToLeastCost()
	{
		int i = 0;
		//前序周游保存
		stack<Node*>astack;
		astack.push(NULL);
		Node*pointer = root;
		while (pointer)
		{
			if (pointer->left != NULL||pointer->right != NULL)  //叶节点的信息复制到编码后的数组中
			{
				sum = sum + pointer->info.oneCost;
			}
			if (pointer->right != NULL)
				astack.push(pointer->right);
			if (pointer->left != NULL)
				pointer = pointer->left;
			else
			{
				pointer = astack.top();
				astack.pop();
			}
		}
	}
	int getleastCost()
	{
		return sum;
	}
};
int main()
{
	LeastCost l;
	int length;
	cin >> length;
	Node *data = new Node[length];
	for (int i = 0; i < length; i++)
	{
		scanf("%d",&(data[i].info.oneCost));
	}
	l.creatTree(data, length);
	l.PreOrderToLeastCost();
    printf("%d",l.getleastCost());
	return 0;
}